// Created by WXX on 2021/9/29 9:36
#include <iostream>
#include <vector>

using namespace std;

/**
 * 执行用时：8 ms, 在所有 C++ 提交中击败了77.40%的用户
 * 内存消耗：12.7 MB, 在所有 C++ 提交中击败了24.86%的用户
 */
class Solution {
public:
    int findMinMoves(vector<int>& w) {
        int s = 0, n = w.size();
        for (int x : w) s += x;
        if (s % n) return -1;

        int avg = s / n, left = 0, right = s;
        int res = 0;
        for (int i = 0; i < n; i++) {
            right -= w[i];
            if (i) left += w[i - 1];
            int l = max(avg * i - left, 0);  // 左边缺少的衣服数量
            int r = max(avg * (n - i - 1) - right, 0);  // 右边缺少的衣服数量
            res = max(res, l + r);
        }
        return res;
    }
};

int main() {

    vector<int> w = {4, 0, 0, 4};
    cout << Solution().findMinMoves(w) << endl;  // 2

    return 0;
}
